#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
    int val;
    ListNode* next;
};
ListNode* Intermediate_node(ListNode* head) {
    ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
ListNode* revers_List(ListNode* node) {
    ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = node;
    n3 = node->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* node = A;
        ListNode* cur = NULL;
        cur = Intermediate_node(A);
        cur = revers_List(cur);
        while (cur && node)
        {
            if (cur->val != node->val)
                return false;
            cur = cur->next;
            node = node->next;
        }
        return true;
    }
};
int main()
{

}